#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
//TOP-K问题
//有10000个数，选出前十大的数
//建立一个大堆，pop9次 
// 
// 1. 建堆--用a中前k个元素建小堆   //小堆可以保证最大的k个数都在堆里
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
 

//交换
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整//前提，左子树和右子树是堆 
void AdjustDown(int* a, int n, int parent)
{	 							//数组大小
	//先假设左孩子小
	int child = parent * 2 + 1;
	while (child < n)//第二个结束条件，孩子数值超出数组界限
	{
		//选出左右孩子中小/大的那个
		if (child + 1 < n && a[child + 1] < a[child])//小根堆
		{//如果没有右孩子，不进入，且&&判定前条件为false
		 //不会再进入后条件，数组不会越界访问
			child++;
		}
		//此时child为小孩子，无需区分左右

		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//第一个结束条件，提前达成堆
		}
	}
}
//堆排序O(N*logN)
void HeapSort(int* a, int n)
{
	//建堆--向上调整建堆O(N*logN)	//计算的次数大概(N+1)*(log(N+1)-2)+2
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);//模拟从第一个数插入，向上调整建堆//此处控制建立大堆小堆
	//}

	//建堆--向下调整建堆O(N)	//计算的次数大概N-log(N+1)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{		//n-1是下标-1/2是父亲
		AdjustDown(a, n, i);//此处控制建立大堆小堆
	}
	// 
	//倒着调整，叶子节点没有孩子，不用向下调整，
	//最后一个节点的父亲开始调整



	//降序-建小堆    升序-建大堆 
	//建堆后选出最小的，与末尾交换，隔离末尾，前半段
	//向下调整，形成小堆，又能选出次小的，与此时末尾交换
	//重复，直到end=0
	for (int end = n - 1; end > 0; end--)//N*logN
	{
		//首尾交换
		Swap(&a[0], &a[end]);
		//向下调整
		AdjustDown(a, end, 0);//logN
		//上一个数组的尾下标，刚好是下一个数组长度
		//后面end--，end又变成了尾下标
	}
}
//造数据
void CreateNDate()
{
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
	//1. 建堆--用a中前k个元素建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);//此处文件指针从k+1开始读
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}
	HeapSort(kminheap, k);
	for (int i = 0; i < k; i++)
	{
		printf("%d\n", kminheap[i]);
	}
}
int main()
{
		CreateNDate();
		PrintTopK(10); 
}